import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCases = Integer.parseInt(br.readLine().trim());
		while(testCases-- != 0) {
			int n = Integer.parseInt(br.readLine());
			int[] stick = new int[n];
			String str = br.readLine().trim();
			for(int i = 0; i < n; i++) {
				if(str.charAt(i) == '1') {
					stick[i] = 1;
				} else {
					stick[i] = 0;
				}
			}
			
			int[][] lookup = new int[n][n];
			for(int i = 0; i < n; i++) {
				lookup[i][i] = stick[i];
			}
			
			for(int k = 1; k < n; k++) {
				for(int i = 0; i < n && i + k < n; i++) {
					lookup[i][i + k] = stick[i + k] == 1 ? lookup[i][i + k - 1] + 1 : lookup[i][i + k - 1]; 
				}
			}
			
			int[] mem = new int[n];
			mem[0] = stick[0] == 1 ? 1 : 0;
			
			for(int i = 1; i < n; i ++) {
				mem[i] = mem[i - 1];
				for(int j = i; j >= 0; j--) {
					if(isBreakable(stick, lookup, j, i)) {
						mem[i] = Math.max(mem[i], (j - 1 >= 0 ? mem[j - 1] : 0) + (i - j) + 1);
					}
				}
			}
			
			System.out.println(mem[n - 1]);
		}
				
	}
	
	private static boolean isBreakable(int[] stick, int[][] lookup, int i, int j) {
		int sweet = lookup[i][j];
		int size = (j - i) + 1;
		return sweet > size / 2; 
	}
}
